Stackelberg games form the core of a number of tools deployed for computing optimal patrolling strategies in adversarial domains, such as the US Federal Air Marshall Service and the US Coast Guard. In traditional Stackelberg security game models the attacker knows only the probability that each target is covered by the defender, but is oblivious to the detailed timing of the coverage schedule. In many real-world situations, however, the attacker can observe the current location of the defender and can exploit this knowledge to reason about the defender’s future moves. We show that this general modeling framework can be captured using adversarial patrolling games (APGs) in which the defender sequentially moves between targets, with moves constrained by a graph, while the attacker can observe the defender’s current location and his (stochastic) policy concerning future moves. We offer a very general model of infinite-horizon discounted adversarial patrolling games. Our first contribution is to show that defender policies that condition only on the previous defense move (i.e., Markov stationary policies) can be arbitrarily suboptimal for general APGs. We then offer a mixed-integer non-linear programming (MINLP) formulation for computing optimal randomized policies for the defender that can condition on history of bounded, but arbitrary, length, as well as a mixed-integer linear programming (MILP) formulation to approximate these, with provable quality guarantees. Additionally, we present a non-linear programming (NLP) formulation for solving zero-sum APGs. We show experimentally that MILP significantly outperforms the MINLP formulation, and is, in turn, significantly outperformed by the NLP specialized to zero-sum games.

Defender-Attacker Stackelberg games are the foundations of toolsdeployed for computing optimal patrolling strategies in adversarialdomains such as the United states Federal Air Marshals Service and the UnitedStates Coast Guard, among others.In Stackelberg game models of these systems the attacker knows only theprobability that each target is covered by the defender, but isoblivious to the detailed timing of the coverage schedule.In many real-world situations, however, the attacker can observe thecurrent location of the defender and can exploit this knowledge toreason about the defender's future moves.We study Stackelberg security games in which the defender sequentiallymoves between targets, with moves constrained by an exogenouslyspecified graph, while the attacker can observe the defender's currentlocation and his (stochastic) policy concerning future moves. We offerfive contributions: (1) We model this adversarial patrolling game (APG) as a stochastic game with special structure and presentseveral alternative formulations that leverage the general non-linearprogramming (NLP) approach for computing equilibria in zero-sumstochastic games. We show that our formulations yield significantlybetter solutions than previous approaches. (2) We extend theNLP formulation for APG allow for attacks that may take multiple timesteps to unfold.(3) We provide anapproximate MILP formulation that uses discrete defender moveprobabilities. (4) We experimentally demonstrate the efficacy of anNLP-based approach, and systematically study the impact of networktopology on the results.(5) We extend our model to allow the defender to construct the graph constraining his moves, at some cost, and offer novel algorithms for this setting, finding that a MILP approximation is much more effective than the exact NLP in this setting.